#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

// Dijkstra算法模版（Leetcode）
// 网络延迟时间
// 有 n 个网络节点，标记为 1 到 n
// 给你一个列表 times，表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi
// 现在，从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号，返回 -1
// 测试链接 : https://leetcode.cn/problems/network-delay-time

class Solution 
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        vector<vector<pair<int, int>>> g(n);
        for(auto& t : times)
        {
            int x = t[0] - 1, y = t[1] - 1, w = t[2];
            g[x].push_back({y, w});
        }


        const int INF = 0x3f3f3f3f;
        vector<int> dist(n, INF);
        dist[k - 1] = 0;
        vector<bool> visited(n);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({0, k - 1});
        while(!q.empty())
        {
            int x = q.top().second;
            q.pop();
            if(visited[x]) continue;
            
            visited[x] = true;
            for(auto& [y, w] : g[x])
            {
                if(!visited[y] && dist[y] > dist[x] + w)
                {
                    dist[y] = dist[x] + w;
                    q.push({dist[y], y});
                }
            }
        }
        
        int ret = *max_element(dist.begin(), dist.end());
        return ret == INF ? -1 : ret;
    }
};